This invention relates to techniques for performing arithmetic in Galois fields, and more particularly to methods of performing multiplication in a computer system.
Applications, including but not limited to popular public-key algorithms, may require arithmetic in Galois fields GF(2k). Among the applications that may require such multiplication are cryptographic schemes based on the assumed intractability of the discrete logarithm in finite fields, elliptic curve discrete logarithm, or hyperelliptic curves. Galois field multiplication is generally considered the most crucial operation for the performance of these cryptosystems.
Many applications, including public-key cryptographic schemes, may require operations in relatively large finite fields; e.g., about 150-250 bits for elliptic curve systems and 1024 or more bits for systems based on the discrete logarithm problem in finite fields. For physical security as well as for performance reasons, implementations of Galois field arithmetic in hardware are generally very attractive. At the same time, the algorithm-independent design paradigm of modem crypto protocols, and flexible security levels require alterable implementations that may be difficult to provide with traditional (non-reconfigurable) hardware.